package cn.fxc.util;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class GraphUtil<T> {
    /**
     * 有向图顶点数据类型泛型
     *
     * @param <T>
     */
    private class Vertex<T> {
        public T data; // 数据
        public Node<T> firstLinkNode; // 第一个邻接节点
        //public boolean visited; // 访问标志,遍历时使用
        public int inDegree; // 表示该节点入度


        public Vertex(T value) {
            data = value;
        }
    }

    /**
     * 有向图关系链表节点
     *
     * @param <T>
     */
    private class Node<T> {
        public Vertex<T> adjvex; //顶点
        public Node<T> next; //下一个邻接点

        /// <summary>
        /// 构造函数
        /// </summary>
        /// <param name="value"></param>
        public Node(Vertex<T> value) {
            adjvex = value;
        }
    }

    /**
     * 有向图表示类
     *
     * @param <T>
     */
    private class AdjacencyList<T> {
        List<Vertex<T>> items; // 图的顶点集合

        public AdjacencyList() {
            items = new ArrayList<>();
        }

        /**
         * 添加顶点
         *
         * @param item
         */
        private void addVertex(T item) {   // 顶点不存在
            if (!items.stream().map(v -> v.data).toList().contains(item)) {
                items.add(new Vertex<>(item));
            }
        }


        /**
         * 添加无向边
         *
         * @param from
         * @param to
         */
        public void addEdge(T from, T to) {
            Vertex<T> fromVer = find(from); //找到起始顶点
            if (fromVer == null)
                throw new RuntimeException("头顶点并不存在！");

            Vertex<T> toVer = find(to); //找到结束顶点
            if (toVer == null)
                throw new RuntimeException("尾顶点并不存在！");

            //无向图的两个顶点都需记录边信息，有向图只需记录单边信息
            //即无相图的边其实就是两个双向的有向图边
            addDirectedEdge(fromVer, toVer);
            addDirectedEdge(toVer, fromVer);
        }

        /**
         * 添加顶点
         *
         * @param data
         * @return
         */
        private Vertex<T> find(T data) {
            for (Vertex<T> v : items) {
                if (v.data.equals(data))
                    return v;
            }
            return null;
        }

        /**
         * 添加有向边
         *
         * @param fromVer 头顶点
         * @param toVer   尾顶点
         */
        private void addDirectedEdge(Vertex<T> fromVer, Vertex<T> toVer) {
            if (fromVer.firstLinkNode == null) //无邻接点时，当前添加的尾顶点就是firstLinkNode
            {
                fromVer.firstLinkNode = new Node<>(toVer);
            } else // 该头顶点已经存在邻接点，则找到该头顶点链表最后一个Node，将toVer添加到链表末尾
            {
                Node<T> tmp;
                Node<T> node = fromVer.firstLinkNode;
                do {   // 检查是否添加了重复有向边
                    if (node.adjvex.data.equals(toVer.data)) {
                        throw new RuntimeException("添加了重复的边！");
                    }
                    tmp = node;
                    node = node.next;
                } while (node != null);
                tmp.next = new Node<>(toVer); //添加到链表末尾
            }
        }

        /**
         * 拓扑排序
         *
         * @return
         */
        public boolean TopologicalSort() {
            Stack<Vertex<T>> stack = new Stack<>(); // 定义栈
            items.forEach(it -> {// 循环顶点集合，将入度为0的顶点入栈

                if (it.inDegree == 0)
                    stack.push(it);         //入度为0的顶点入栈

            });
            int count = 0;   // 定义查找到的顶点总数
            while (!stack.isEmpty()) {
                Vertex<T> t = stack.pop();  // 出栈
                count++;
                if (t.firstLinkNode != null) {
                    Node<T> tmp = t.firstLinkNode;
                    while (tmp != null) {
                        tmp.adjvex.inDegree--;  // 邻接点入度-1
                        if (tmp.adjvex.inDegree == 0) // 如果邻接点入度为0，则入栈
                            stack.push(tmp.adjvex);
                        tmp = tmp.next; // 递归所有邻接点
                    }
                }
            }
            // 找到的结果数量小于图顶点个数相同，表示拓扑排序失败，表示有闭环
            return count >= items.size();
        }
    }

    /**
     * 验证是否有回路
     *
     * @param originalData
     * @return
     */
    public boolean checkDigraphHasLoop(List<T[]> originalData) {
        AdjacencyList<T> adjacencyList = new AdjacencyList<>();
        T fromData;
        T toData;

        //构造有向图的邻接表表示
        for (T[] it : originalData) {
            fromData = it[0]; //得到from顶点数据
            toData = it[1];   //得到to定点数据
            adjacencyList.addVertex(fromData);
            adjacencyList.addVertex(toData);

            Vertex<T> fromVertex = adjacencyList.find(fromData); // 找到起始顶点
            Vertex<T> toVertex = adjacencyList.find(toData); // 找到目标顶点
            if (fromVertex != null && toVertex != null) {
                toVertex.inDegree++; //目标顶点的入度+1
                adjacencyList.addDirectedEdge(fromVertex, toVertex); //添加有向边
            }
        }

        return !(adjacencyList.TopologicalSort());
    }

    public static void main(String[] args) {
        List<String[]> temp1 = new ArrayList<>();
        temp1.add(new String[]{"1", "2"});
        temp1.add(new String[]{"2", "3"});
        temp1.add(new String[]{"1", "3"});
        temp1.add(new String[]{"3", "4"});
        temp1.add(new String[]{"1", "4"});
        temp1.add(new String[]{"4", "2"});
        GraphUtil g = new GraphUtil();
        boolean result = g.checkDigraphHasLoop(temp1);
        System.out.println(result);

        List<Integer[]> temp2 = new ArrayList<>();
        temp2.add(new Integer[]{1, 2});
        temp2.add(new Integer[]{2, 3});
        temp2.add(new Integer[]{1, 3});
        g = new GraphUtil();
        result = g.checkDigraphHasLoop(temp2);
        System.out.println(result);
    }
}
